/*
 * @lc app=leetcode.cn id=1239 lang=typescript
 *
 * [1239] 串联字符串的最大长度
 */

// @lc code=start
function maxLength(arr: string[]): number {
  // 保存每个元素的二进制位，来判断是否出现过某个字符
  const masks = [];

  // 删选arr中无重复字符的字符串
  for (const s of arr) {
    let mask = 0;
    for (let i = 0; i < s.length; i++) {
      const code = s.charCodeAt(i) - 'a'.charCodeAt(0);
      if (((mask >> code) & 1) !== 0) {
        mask = 0;
        break;
      }
      mask |= 1 << code;
    }
    if (mask > 0) masks.push(mask);
  }

  const dfs = (masks: number[], i: number, mask: number) => {
    // 找到最后，都没有重复的元素，更新答案
    if (i === masks.length) {
      ans = Math.max(ans, mask.toString(2).split('0').join('').length);
      return;
    }
    // 如果无重复的，继续累加下一个元素检测
    if ((masks[i] & mask) === 0) {
      dfs(masks, i + 1, masks[i] | mask);
    }
    // 有重复的，跳过当前元素，继续开一个检测
    dfs(masks, i + 1, mask);
  };

  let ans = 0;
  dfs(masks, 0, 0);
  return ans;
}
// @lc code=end
